

def insert_sort(nums):
    for i in range(len(nums)-1):
        j = i+1
        count = 0
        while j > 0 and nums[j] < nums[j-1]:
            nums[j],nums[j-1] = nums[j-1],nums[j]
            j -= 1
            count += 1
        print(f"{i}次=",nums,count)
    return nums

# print(insert_sort([5,4,3,2,1]))
print(insert_sort([3,1,2,4,5]))

'''
时间复杂度：最优：O(n) 最坏：O(n^2)
空间复杂度：O(1)
'''